package dp

// BackTraceClimbingStairs 回溯爬楼梯
func BackTraceClimbingStairs(n int) int {
	choices := []int{1, 2}
	var result, current int
	climbingStairsBT(choices, &current, &result, n)
	return result
}

func climbingStairsBT(choices []int, current, result *int, n int) {
	if *current == n {
		*result += 1
		return
	}
	for _, choice := range choices {
		if *current+choice > n {
			break
		}
		*current += choice
		climbingStairsBT(choices, current, result, n)
		*current -= choice
	}
}

// DfsClimbingStairs dfs 爬楼梯
func DfsClimbingStairs(n int) int {
	return climbingStairsDfs(n)
}

func climbingStairsDfs(n int) int {
	if n <= 2 {
		return n
	}

	return climbingStairsDfs(n-1) + climbingStairsDfs(n-2)
}

// DfsClimbingStairsMem 增加缓存爬楼梯
func DfsClimbingStairsMem(n int) int {
	return climbingStairsDfsMem(n, make(map[int]int, n-2))
}

func climbingStairsDfsMem(n int, mem map[int]int) int {
	if n <= 2 {
		return n
	}

	if val, ok := mem[n]; ok {
		return val
	}

	res := climbingStairsDfs(n-1) + climbingStairsDfs(n-2)
	mem[n] = res
	return res
}

func DpClimbingStairs(n int) int {
	if n <= 2 {
		return n
	}
	// 状态方程 dp[n] = dp[n-2] + dp[n-1]
	dp := make([]int, n+1)
	dp[1] = 1
	dp[2] = 2
	for i := 3; i < len(dp); i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

func OptimizeDpClimbingStairs(n int) int {
	if n <= 2 {
		return n
	}
	var res int
	dp1, dp2 := 1, 2
	for i := 3; i <= n; i++ {
		res = dp1 + dp2
		dp1 = dp2
		dp2 = res
	}
	return res
}

// 每次可以跳一步或者两步，不能连续跳两次一步
func climbingStairsConstraintDP(n int) int {
	//状态方程
	// dp[i,1] = dp[i-1,2]
	// dp[i,2] = dp[i-2,1] + dp[i-2,2]

	if n <= 2 && n > 0 {
		return 1
	}
	dp := make([][3]int, n+1)

	dp[1][1] = 1
	dp[2][2] = 1

	for i := 3; i <= n; i++ {
		dp[i][1] = dp[i-1][2]
		dp[i][2] = +dp[i-2][1] + dp[i-2][2]
	}
	return dp[n][1] + dp[n][2]
}
